package leetcode.editor.cn;
import java.util.*;
//给你一个字符串 s ，请你找到 s 中两个 不相交回文子序列 ，使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符，则它们是 不相
//交 的。 
//
// 请你返回两个回文子序列长度可以达到的 最大乘积 。 
//
// 子序列 指的是从原字符串中删除若干个字符（可以一个也不删除）后，剩余字符不改变顺序而得到的结果。如果一个字符串从前往后读和从后往前读一模一样，那么这个字符
//串是一个 回文字符串 。 
//
// 
//
// 示例 1： 
//
// 
//
// 输入：s = "leetcodecom"
//输出：9
//解释：最优方案是选择 "ete" 作为第一个子序列，"cdc" 作为第二个子序列。
//它们的乘积为 3 * 3 = 9 。
// 
//
// 示例 2： 
//
// 输入：s = "bb"
//输出：1
//解释：最优方案为选择 "b" （第一个字符）作为第一个子序列，"b" （第二个字符）作为第二个子序列。
//它们的乘积为 1 * 1 = 1 。
// 
//
// 示例 3： 
//
// 输入：s = "accbcaxxcxx"
//输出：25
//解释：最优方案为选择 "accca" 作为第一个子序列，"xxcxx" 作为第二个子序列。
//它们的乘积为 5 * 5 = 25 。
// 
//
// 
//
// 提示： 
//
// 
// 2 <= s.length <= 12 
// s 只含有小写英文字母。 
// 
// Related Topics 位运算 字符串 动态规划 回溯 状态压缩 👍 13 👎 0

public class 两个回文子序列长度的最大乘积{
	public static void main(String[] args) {
		Solution solution = new 两个回文子序列长度的最大乘积().new Solution();
	    solution.maxProduct("leetcodecom");
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxProduct(String s) {
		char[] chars = s.toCharArray();
		int length = s.length();
		//1.首先统计所有满足回文子序列条件的状态
		ArrayList<Integer> list = new ArrayList<>();
		//可能的状态总数n，什么都不选也是一种状态
		int n = 1 << length;
		for (int i = 0; i < n; i++) {
			if(check(chars, i)){
				System.out.println(i);
				list.add(i);
			}
		}
		//2.对list两两组合，找到不相交并乘积最大的那个
		int max = Integer.MIN_VALUE;
		for (Integer i : list) {
			for (Integer j : list) {
				// 判断是否重复使用某个数
				if((i&j)!=0){
					continue;
				}
				else {
					//子任务：统计二进制中1的个数
					int a = getNumber(i);
					int b = getNumber(j);
					max = Math.max(max, a*b);
				}
			}
		}
		return max;
	}
	public boolean check(char[] chars, int i){
		int left = 0;
		int right = chars.length-1;
		while (left < right){
			while (left<right && ((1 << left)&i)==0){
				left++;
			}
			while (left<right && ((1 << right)&i)==0){
				right--;
			}
			if(chars[left]!=chars[right]){
				return false;
			}
			left++;
			right--;
		}
    	return true;
	}

	public int getNumber(int i){
    	// 减一 + 与运算
		int res = 0;
		while (i!=0){
			i = i & (i-1);
			res++;
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
